package problems.contest;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * 第 359 场周赛
 * @author dubulingbo, 2023/8/20 9:55.
 */
public class WCT359 {
    /**
     * T1|
     */
    public boolean isAcronym(List<String> words, String s) {
        if (s.length() != words.size()) return false;
        int n = s.length();

        for (int i = 0; i < n; ++i) {
            if (s.charAt(i) != words.get(i).charAt(0)) return false;
        }

        return true;
    }


    public int minimumSum(int n, int k) {
        HashSet<Integer> set = new HashSet<>();
        int sum = 0;
        int i = 1;

        while (set.size() < n) {
            if (!set.contains(k - i)) {
                set.add(i);
                sum += i;
            }
            ++i;
        }

        return sum;
    }

    public int maximizeTheProfit(int n, List<List<Integer>> offers) {
        // 按 end 进行非递减排序
        offers.sort((o1, o2) -> Integer.compare(o1.get(1), o2.get(1)));
        int sz = offers.size();
        // dp[i] 表示编号 0-i 的房子卖出去能获得的最大利益
        int[] dp = new int[n + 1];

        int k = 0;

        for (int i = 1; i <= n; ++i) {
            // 如果编号为 i 的房子没卖出去，那么最大利益就是编号 0~(i-1) 的房子卖出去的最大利益
            dp[i] = dp[i - 1];
            // 遍历剩下的客户满足需求的end，注意
            while (k < sz && offers.get(k).get(1) < i) {
                dp[i] = Math.max(dp[i], dp[offers.get(k).get(0)] + offers.get(k).get(2));
                ++k;
            }
        }

        return dp[n];
    }
}
